//////////////////////////////////////
// Fast Container Library           //
// MIT License - Copyright (c) 2012 //
//////////////////////////////////////

#pragma once

#include "common.h"
#include "bit_base.h"
#include "forward.h"

FC_NAMESPACE_BEGIN



template<size_t NWords>
class bitset_base
{
public:
	typedef bitset_base<NWords>		this_type;
	typedef size_t					size_type;

	enum : size_t
	{
		NBits = FC_INT32_BITCOUNT(NWords),
		word_count = NWords,
		size_bits = 32,
		size_mask = 31,
		size_shift = 5
	};

	bitset_base()
		{
			reset();
		}

	bitset_base( size_t value )
		{
			m_bits[0] = value;
		}

	void operator <<=( size_t n )
	{
		const size_t s = size_t(n >> size_shift);
		if( s != 0 )
			for( size_t i(NWords - 1); i >= 0; --i )
				m_bits[i] = (s <= i) ? m_bits[i - s] : size_t(0);

		n &= size_mask;
		if( n != 0 )
		{
			for( size_t i(NWords - 1); i > 0; --i )
				m_bits[i] = (size_t)((m_bits[i] << n) | (m_bits[i - 1] >> (size_mask - n)));
			m_bits[0] <<= n;
		}
	}

	void operator >>=( size_t n )
	{
		const size_t s = (size_t)(n >> size_shift);
		if( s != 0 )
			for(size_t i = 0; i < NWords; ++i)
				m_bits[i] = ((s < (NWords - i)) ? m_bits[i + s] : (size_t)0);

		n &= size_mask;
		if( n != 0 )
		{
			for( size_t i(0); i < (NWords - 1); ++i)
				m_bits[i] = (size_t)((m_bits[i] >> n) | (m_bits[i + 1] << (size_mask - n)));
			m_bits[NWords - 1] >>= n;
		}
	}

	void operator &=( const this_type& x )
	{
		for( size_t i(0); i < NWords; ++i )
			m_bits[i] &= x.m_bits[i];
	}

	void operator |=( const this_type& x )
	{
		for( size_t i(0); i < NWords; ++i )
			m_bits[i] |= x.m_bits[i];
	}

	void operator ^=( const this_type& x )
	{
		for( size_t i(0); i < NWords; ++i )
			m_bits[i] ^= x.m_bits[i];
	}

	void flip()
	{
		for( size_t i(0); i < NWords; ++i )
			m_bits[i] = ~m_bits[i];
	}

	void flip( size_t pos )
	{
		m_bits[pos >> size_shift] ^= size_type(1) << (pos & size_mask);
	}

	void set()
	{
		for( size_t i(0); i < NWords; ++i )
			m_bits[i] = size_type(-1);
	}

	void set( size_t pos, bool value )
	{
		bit_reference( &m_bits[pos >> size_shift], pos ) = value;
	}

	void reset()
	{
		for( size_t i(0); i < NWords; ++i )
			m_bits[i] = size_type(0);
	}

	bool operator ==( const this_type& x ) const
	{
		for( size_t i(0); i < NWords; ++i )
			if( m_bits[i] != x.m_bits[i] )
				return false;

		return true;
	}

	bool any() const
	{
		for( size_t i(0); i < NWords; ++i )
			if( m_bits[i] != size_type(0) )
				return true;

		return false;
	}

	bool test( size_t pos ) const
	{
		return (m_bits[pos >> size_shift] & (size_type(1) << (pos & size_mask))) != 0;
	}

	size_t count() const
	{
		size_t n = 0;
		for( size_t i(0); i < NWords; ++i )
			n += fc::count_bits(m_bits[i]);

		return n;
	}

	size_t* data() { return &m_bits[0]; }
	const size_t* data() const { return &m_bits[0]; }

protected:
	size_t m_bits[NWords];

};


template<>
class bitset_base<1>
{
public:
	typedef bitset_base<1>		this_type;
	typedef size_t				size_type;

	enum : size_t
	{
		size_bits = 32,
		size_mask = 31,
		size_shift = 5
	};

	bitset_base() : m_bits(0) {}
	bitset_base( size_t value ) : m_bits(value) {}

	void operator <<=( size_t n ) { m_bits <<= n; }
	void operator >>=( size_t n ) { m_bits >>= n; }
	void operator &=( const this_type& x ) { m_bits &= x.m_bits; }
	void operator |=( const this_type& x ) { m_bits |= x.m_bits; }
	void operator ^=( const this_type& x ) { m_bits ^= x.m_bits; }

	void flip( size_t pos ) { m_bits ^= size_type(1) << pos; }
	void flip() { m_bits = ~m_bits; }
	void reset() { m_bits = size_type(0); }
	void set() { m_bits = ~size_type(0); }
	void set( size_t pos, bool value )
	{
		if(value)
			m_bits |= (size_t(1) << pos);
		else
			m_bits &= ~(size_t(1) << pos);
	}

	size_t count() const { return fc::count_bits(m_bits); }

	bool operator ==( const this_type& x ) const { return m_bits == x.m_bits; }
	bool any() const { return m_bits != size_t(0); }
	bool test( size_t pos ) const
	{
		return (m_bits & (size_type(1) << pos)) != 0;
	}

	size_t* data() { return &m_bits; }
	const size_t* data() const { return &m_bits; }

protected:
	size_t m_bits;

};


template<>
class bitset_base<2>
{
public:
	typedef bitset_base<2>		this_type;
	typedef size_t				size_type;

	enum : size_t
	{
		size_bits = 64,
		size_mask = 63,
		size_shift = 6
	};

	bitset_base() : m_bits(0) {}
	bitset_base( size_t value ) : m_bits(uint64_t(value)) {}

	void operator <<=( size_t n ) { m_bits <<= n; }
	void operator >>=( size_t n ) { m_bits >>= n; }
	void operator &=( const this_type& x ) { m_bits &= x.m_bits; }
	void operator |=( const this_type& x ) { m_bits |= x.m_bits; }
	void operator ^=( const this_type& x ) { m_bits ^= x.m_bits; }

	void flip( size_t pos ) { m_bits ^= uint64_t(uint64_t(1) << pos); }
	void flip() { m_bits = ~m_bits; }
	void reset() { m_bits = uint64_t(0); }
	void set() { m_bits = ~uint64_t(0); }
	void set( size_t pos, bool value )
	{
		if(value)
			m_bits |= uint64_t(uint64_t(1) << pos);
		else
			m_bits &= ~uint64_t(uint64_t(1) << pos);
	}

	size_t count() const { return fc::count_bits(m_bits); }

	bool operator ==( const this_type& x ) const { return m_bits == x.m_bits; }
	bool any() const { return m_bits != uint64_t(0); }
	bool test( size_t pos ) const
	{
		return (m_bits & uint64_t(uint64_t(1) << pos)) != uint64_t(0);
	}

	size_t* data() { return (size_t*)&m_bits; }
	const size_t* data() const { return (size_t*)&m_bits; }

protected:
	uint64_t m_bits;

};


/**
 * @ non-standard (but still extremely) compliant bitset class.
 * *note* optimized template specializations are given for
 * bitset<1-64> sizes.
 **/

template<size_t N>
class bitset : protected bitset_base<FC_INT32_WORDCOUNT(N)>
{
public:
	typedef bitset<N>							this_type;
	typedef bitset_base<FC_INT32_WORDCOUNT(N)>	base_type;
	typedef size_t								size_type;
	typedef bit_reference						reference;

	bitset()
		: base_type()
		{
		}

	bitset( size_t value )
		: base_type(value)
		{
			trim();
		}

	this_type& operator <<=( size_t n )
	{
		base_type::operator <<=(n);
		trim();
		return *this;
	}

	this_type& operator >>=( size_t n )
	{
		base_type::operator >>=(n);
		return *this;
	}

	this_type& operator &=( const this_type& x )
	{
		base_type::operator &=(x);
		return *this;
	}

	this_type& operator |=( const this_type& x )
	{
		base_type::operator |=(x);
		return *this;
	}

	this_type& operator ^=( const this_type& x )
	{
		base_type::operator ^=(x);
		return *this;
	}

	this_type operator <<( size_t n ) const { return this_type(*this).operator <<=(n); }
	this_type operator >>( size_t n ) const { return this_type(*this).operator >>=(n); }

	this_type operator |( const this_type& x ) const { return this_type(*this).operator |= (x); }
	this_type operator &( const this_type& x ) const { return this_type(*this).operator &= (x); }
	this_type operator ^( const this_type& x ) const { return this_type(*this).operator ^= (x); }
	this_type operator ~() const { return this_type(*this).flip(); }

	reference operator []( size_t pos ) { return reference(*this, pos); }
	bool operator []( size_t pos ) const { return base_type::test(pos); }

	reference at( size_t pos ) { return reference(*this, pos); }
	bool at( size_t pos ) const { return base_type::test(pos); }

	this_type& flip()
	{
		base_type::flip();
		return *this;
	}

	this_type& flip( size_t pos )
	{
		base_type::flip(pos);
		trim();
		return *this;
	}

	this_type& set()
	{
		base_type::set();
		trim();
		return *this;
	}

	this_type& set( size_t pos, bool value = true )
	{
		FC_ASSERT(pos < N);
		base_type::set(pos, value);
		return *this;
	}

	this_type& reset()
	{
		base_type::reset();
		return *this;
	}

	this_type& reset( size_t pos )
	{
		FC_ASSERT(pos < N);
		base_type::set(pos, false);
		return *this;
	}

	bool operator ==( const this_type& x ) const { return base_type::operator ==(x); }
	bool operator !=( const this_type& x ) const { return !(*this == x); }

	bool any() const { return base_type::any(); }
	bool none() const { return !base_type::any(); }
	bool test( size_t pos ) const { return operator [](pos); }

	size_t count() const { return base_type::count(); }
	size_t size() const { return N; }

	size_t* data() { return base_type::data(); }
	const size_t* data() const { return base_type::data(); }

	FC_FORCE_INLINE void trim()
	{
		//this is required to knock off any extra bits when N is not a multiple of word size.
		if( N & base_type::size_mask )
			*(base_type::data() + (FC_INT32_WORDCOUNT(N) - 1)) &= ~(~size_t(0) << (N & base_type::size_mask));
	}

};


FC_NAMESPACE_END

